//Sunday, November 01 2009
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <algorithm>

using namespace std;

class MagicWords
{
public:
	vector<int> mp;
	int count(vector <string> S, int K)
	{
		int ret = 0;
		for(int i=0; i<S.size(); i++)
			mp.push_back(i);
		//sort(mp.begin(), mp.end());
		do
		{
			string temp = "";
			for(int i=0; i<S.size(); i++)
				temp += S[mp[i]];
			if(check(temp, K))
				ret++;
		}
		while(next_permutation(mp.begin(), mp.end()));
		return ret;
	}

	bool check(string s, int K)
	{
// 		int cnt = 0;
// 		for(int i=0; i<s.size(); i++)
// 		{
// 			if(s[i] == s[0])
// 			{
// 				string temp = s.substr(i) + s.substr(0,i);
// 				if(temp.compare(s) == 0) cnt++;
// 			}
// 		}
//		return cnt==K;
		int d = (s.substr(1) + s).find(s) + 1;
		return K*d == s.size();
	}
};
